4.1 Permutation
Fundamental Counting Principle
If an event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events can occur together in $m \times n$ ways.
Factorial Notation
The product of the first $n$ positive integers is defined as $n$ factorial ($n!$):
$$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$$
Note: By definition, $0! = 1$.
Permutations of $n$ Distinct Objects
The number of arrangements of $n$ distinct objects taken all at a time is:
$$P_n = n!$$
Permutations of $n$ Distinct Objects Taken $r$ at a Time
The number of permutations of $n$ distinct objects taken $r$ at a time ($0 \le r \le n$) is:
$$^n P_r = \frac{n!}{(n - r)!}$$
Permutations with Restrictions
- Identical Objects: The number of permutations of $n$ objects where $p$ are of one type, $q$ are of another type, and $r$ are of a third type is:
$$P = \frac{n!}{p! \, q! \, r!}$$
- Objects Must Be Together: Group the restricted objects as a single entity, perform the overall permutation, and multiply by the internal permutations within the group.
- Objects Cannot Be Adjacent: Arrange the unrestricted objects first, then insert the restricted objects into the available spaces created between/around them.
- Circular Permutations: The number of permutations of $n$ distinct objects arranged in a circle is $(n - 1)!$. If clockwise and counter-clockwise arrangements are identical (e.g., beads on a necklace), the number of permutations is $\frac{(n - 1)!}{2}$.
4.2 Combination
Definition of Combination
A combination is a selection of items where the order of selection does not matter.
Combinations of $n$ Distinct Objects Taken $r$ at a Time
The number of ways to select $r$ objects from $n$ distinct objects is:
$$^n C_r = \binom{n}{r} = \frac{n!}{r!(n - r)!} = \frac{^n P_r}{r!}$$
Key Properties of Combinations
- $^n C_0 = 1$ and $^n C_n = 1$
- $^n C_1 = n$
- $^n C_r = ^n C_{n-r}$
- $^n C_{r-1} + ^n C_r = ^{n+1} C_r$
Combinations with Conditions
- Selecting Subgroups: If choosing $r_1$ items from group $A$ (size $n_1$) and $r_2$ items from group $B$ (size $n_2$), the total combinations are:
$$\text{Total} = ^{n_1} C_{r_1} \times ^{n_2} C_{r_2}$$
- "At Least" or "At Most" Conditions: Calculate each valid combination scenario separately and sum the results (using the Addition Principle).